package graph;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/*
 *@description 除法求值
 *@author hkfan
 *@version 1.0
 *@create 2025/6/16 15:36
 */
public class LeetCode_399 {

    class Node{
        String value;
        List<Edge> edges;
        int visited;

        public Node(String value) {
            this.value = value;
            this.visited = 0;
            this.edges = new ArrayList<>();
        }
    }

    class Edge{
        Node from;
        Node to;
        double value;

        public Edge(Node from, Node to, double value) {
            this.from = from;
            this.to = to;
            this.value = value;
        }
    }

    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        //1. 定义
        Map<String,Node> nodeMap = new HashMap<>();
        double[] res = new double[queries.size()];
        //2. 加入nodeMap
        for (List<String> equation : equations) {
            nodeMap.put(equation.get(0),nodeMap.getOrDefault(equation.get(0),new Node(equation.get(0))));
            nodeMap.put(equation.get(1),nodeMap.getOrDefault(equation.get(1),new Node(equation.get(1))));
        }
        //3. node中加入edge
        for (int i = 0; i < equations.size(); i++) {
            Node from = nodeMap.get(equations.get(i).get(0));
            Node to = nodeMap.get(equations.get(i).get(1));
            from.edges.add(new Edge(from,to,values[i]));
            to.edges.add(new Edge(to,from,1/values[i]));

        }
        //4. 遍历queries
        for (int i = 0; i < queries.size(); i++) {
            value=-1.0;
            if (nodeMap.containsKey(queries.get(i).get(0)) && nodeMap.containsKey(queries.get(i).get(1))){
                initMap(nodeMap);
                Node from = nodeMap.get(queries.get(i).get(0));
                Node to = nodeMap.get(queries.get(i).get(1));
                search(from,to,1);
            }
            res[i] = value;
        }
        return res;
    }



    private void initMap(Map<String, Node> nodeMap) {
        for (Node node : nodeMap.values()) {
            node.visited=0;
        }
    }


    double value;

    private void search(Node from, Node to,double sum) {
        if (from == to){
            value=sum;
            return;
        }
        from.visited=1;
        for (Edge edge : from.edges) {
            Node next = edge.to;
            if (to.visited==0){
                search(next,to,sum*edge.value);
            }
        }
    }

}
